The present invention relates to a method for determining an optimum solution in a computer-aided scheduling system in various scheduling works.
An optimization technique in a scheduling problem is discussed, for example, in a book titled "INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH", Volume 26, No. 5 (1988), pp. 821-844.
In this technique, an initial solution generated by a certain method is modified using a special algorithm to obtain another solution while satisfying constraints to thereby improve the evaluation value of the solution. According to the aforementioned algorithm for the modification, operations for an assignment method different from the resource assignment method used in generating the initial solution that cause resource competition are listed up to estimate an evaluation value, and if an improvement in the evaluation value can be expected, modification is made to the new assignment method.
This system is intended to solve a scheduling problem as a sort of search problem, that is, to apply operations backwardly from the goal to sequentially generate nodes and to thereby search a solution. In this case, in the above technique, its evaluation function includes a parameter indicative of a total value of processing times.
In the above technique, an evaluation function f* at each node n is considered to comprise two components of cost g* taken from a start node to node n and cost h* taken from node n to a target node, and a node providing a minimum of f* is selected for expansion. However, it is difficult to accurately calculate the evaluation function f* for estimating halfway the evaluation value of a solution at the time of completion of the scheduling process and the function cannot be often obtained during scheduling. Further, since solution searching is carried out by applying operations backwardly from the goal to sequentially generate nodes, the technique has a drawback that, in a practical scheduling problem, a lot of calculation time is required to find an optimal solution.
The technique also has another drawback that, in spite of the fact that it is necessary to consider several evaluation items in an actual problem, only one sort of evaluation item relating to a total processing time is taken into consideration and it is impossible to sequentially handle a plurality of evaluation functions.